---
title: "答疑"
created: 2025-11-28
tags:
  - 算法
---

# 答疑

## 题目 [答疑](https://www.lanqiao.cn/paper/3839/problem/1025/)

![[image-02668cd2.png]]

## 思路分析

模拟了一下案例 顺序是132得到的2.8s

贪心吗 1 3 2的顺序是3s 8s 9s 总时间排序？

有个前缀和的思路在里面

原本发信息的时间只和自己的进入和答疑时间有关 但是后面的人 要累加上前面已经做过的人的进入和答疑时间以及离开时间 也就是总时间

所以分为两部分

一是固有的（必须要用的时间）——所有人的进入和答疑时间之和

二是因为顺序不同 需要等待的时间 如果某人排在第一位 就需要把它的总时间\*总人数 所有人都要等这段时间

贪心也在这里得到证明 高权值配低消耗 总结果最小

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long LL;
const int N=1010;
int si[N],ai[N],ei[N];
LL sumi[N];

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n;cin>>n;
	LL must=0; //必须时间
	for(int i=0;i<n;i++){
        cin>>si[i]>>ai[i]>>ei[i];
        sumi[i]=si[i]+ai[i]+ei[i];
        must+=si[i]+ai[i]; // 累加进入和答疑时间到 d，离开时间不计入
    }

    sort(sumi,sumi+n);

    LL sum=must;//总时间为 固有时间加等待时间
    int t=n;
    for(int i=0;i<n-1;i++){//等待时间与顺序有关  看后面有多少人
    	sum+=(t-1)*sumi[i];
    	t--;
	}

	cout<<sum;

	return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[游园安排|游园安排]] 🏠 [[00-冲刺国赛]] ➡️ [[出租车|出租车]]